Stelling van Euclides

De stelling van Euclides is een wiskundige stelling en zegt dat er oneindig veel priemgetallen zijn. De stelling is naar de Griekse wiskundige Euclides genoemd, die de stelling in zijn werk Elementen in boek IX als propositie 20 noemt.

Bewijs uit het ongerijmde 

Het is een bewijs uit het ongerijmde

Stel dat het aantal priemgetallen eindig is, dus dat alleen de getallen $p_{0},p_{1},\dots ,p_{k}$ een priemgetal zijn. Vermenigvuldig deze $k$ priemgetallen met elkaar en tel er 1 bij op, zodat het product $n=p_{0}\cdot p_{1}\cdot \ldots \cdot p_{k}+1$ ontstaat.

1. $n$ is groter dan het grootste priemgetal in de rij $p_{0},p_{1},\dots ,p_{k}$, dus is het geen priemgetal.
2. $n$ kan daarentegen door geen van de priemgetallen $p_{0},p_{1},\dots ,p_{k}$ worden gedeeld, omdat $n\ {\text{mod}}\ p_{k}=1$ voor alle $k$.

Ieder positieve, gehele getal kan volgens de hoofdstelling van de rekenkunde door tenminste een priemgetal groter dan een worden gedeeld, al is het door zichzelf. Dat betekent een tegenspraak tussen 1 en 2, dus kan de veronderstelling dat er een eindig aantal priemgetallen is niet waar zijn.